package binary_tree.Leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
 *优化使用Map存储节点的高度值
 */
public class Num110_BalancedTree<map> {
private Map<TreeNode,Integer> NodeHeightMap= new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        //边界
        if(root==null){
            return true;
        }
        int left=0;
        int right=0;
        if(NodeHeightMap.containsKey(root.left)){
            //说明此时root.left的高度已经计算过来 直接取出即可
            left=NodeHeightMap.get(root.left);
        }else {
            left=height(root.left);
            NodeHeightMap.put(root.left,left);
        }
        if(NodeHeightMap.containsKey(root.right)){
            right=NodeHeightMap.get(root.right);
        }else {
            right=height(root.right);
            NodeHeightMap.put(root.right,right);
        }
        int value=Math.abs(left-right);
        //root左子树和右子树高度差等于1
        if(value>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    /**
     * 计算以root为根节点的二叉树的高度
     * @param root
     * @return
     */
    public static int height(TreeNode root){
        //边界条件
        if(root==null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));
    }
}
